'''
Created on Mar 26, 2013

@author(s): Nathan Brazee
            Kenneth Stewart II
'''

import sys
import copy
import math

'''
    The board representation contains:
    -number of rows/columns
    -the game grid represented as a 2D array
    -start/end locations
'''
class Board:
    def __init__(self):
        self.rows = 0
        self.columns = 0
        self.grid = []
        self.start = [0,0]
        self.goal = [0,0]

    def output(self):
        print "The board state: "
        for i in range(0, self.rows):
            for j in range(0, self.columns):
                print self.grid[i][j] ,
            print ""
        print ""
                
    def addRow(self, line):
        self.columns = len(line)
        self.rows = self.rows + 1
        newRow = []
        i = 0
        for character in line:
            if (character != "\n"):
                newRow = newRow + [character]
                if (character == "S"):
                    self.start[0] = i
                    self.start[1] = self.rows-1
                elif (character == "G"):
                    self.goal[0] = i
                    self.goal[1] = self.rows-1
                i = i + 1
        self.grid.append(newRow)
    
    def makeMove(self, x, y, value):
            self.grid[y][x] = value
            
    def getRows(self):
        return self.rows
    
    def getColumns(self):
        return self.columns
    
    def getGrid(self):
        return self.grid
    
    def getStart(self):
        return self.start
    
    def getGoal(self):
        return self.goal

'''
    Node class contains:
    -node die
    -node position
    -node path cost
    -the board representation
'''     
class Node:
    def __init__(self, nodePosition, nodeDie, theBoard):
        self.die = nodeDie
        self.position = nodePosition
        self.gx = 0
        self.path = []
        self.board = theBoard
        
    def getLegalMoves(self):
        legal = ["N", "S", "E", "W"]
        i = 0
        while i < len(legal):
            #Check that 6 wont face up
            if (self.die.isValid(legal[i]) == False):
                legal.pop(i)
                continue
            elif (legal[i] == "N"):
                #Check for edge of board
                if (self.position[1] == 0):
                    legal.pop(i)
                    continue
                #Check for obstacle
                else:
                    if (self.board.getGrid()[self.position[1]-1][self.position[0]] == "*"):
                        legal.pop(i)
                        continue
            elif (legal[i] == "S"):
                #Check for edge of board
                if (self.position[1] >= self.board.getRows()-1):
                    legal.pop(i)
                    continue
                #Check for obstacle
                else:
                    if (self.board.getGrid()[self.position[1]+1][self.position[0]] == "*"):
                        legal.pop(i)
                        continue
            elif (legal[i] == "E"):
                #Check for edge of board
                if (self.position[0] == self.board.getColumns()-1):
                    legal.pop(i)
                    continue
                #Check for obstacle
                else:
                    if (self.board.getGrid()[self.position[1]][self.position[0]+1] == "*"):
                        legal.pop(i)
                        continue
            elif (legal[i] == "W"):
                #Check for edge of board
                if (self.position[0] == 0):
                    legal.pop(i)
                    continue
                #Check for obstacle
                else:
                    if (self.board.getGrid()[self.position[1]][self.position[0]-1] == "*"):
                        legal.pop(i)
                        continue
            i = i + 1
        return legal
    
    def getNeighbors(self):
        neighborNodes = []
        legalMoves = self.getLegalMoves()
        #print 'Node position: ' + str(self.position) + '\nNode legal moves: ' + str(legalMoves) + '\n'
        for direction in legalMoves:
            n = copy.deepcopy(self)
            n.move(direction)
            neighborNodes.append(n)
        return neighborNodes
                
    def move(self, direction):
        #Adjust the current position tuple
        if (direction == "N"):
            self.position[1] = self.position[1] - 1
        elif (direction == "S"):
            self.position[1] = self.position[1] + 1
        elif (direction == "E"):
            self.position[0] = self.position[0] + 1
        elif (direction == "W"):
            self.position[0] = self.position[0] - 1
        #Change the die position)
        self.die.move(direction)
        self.gx = self.gx + 1
        self.path = self.path + [copy.deepcopy(self.position) + [direction]]
    
    def matches(self, node):
        if ((self.position == node.getPosition()) and (self.die.matches(node.getDie()))):
            return True
        return False
    
    def getDie(self):
        return self.die
    
    def getPosition(self):
        return self.position
    
    def getGx(self):
        return self.gx
    
    def getPath(self):
        return self.path
        
'''Die class contains:
    -number values for every face of the die'''
class Die:
    def __init__(self):
        self.up = 1
        self.down = 6
        
        self.north = 2
        self.south = 5
        
        self.east = 3
        self.west = 4
        
    def move(self, direction):
        #Upward facing side of the die flips South
        if (direction == "S"):
            newUp = self.north
            newDown = self.south
            newNorth = self.down
            newSouth = self.up
            newEast = self.east #no change
            newWest = self.west #no change
        #Upward facing side of the die flips North
        elif (direction == "N"):
            newUp = self.south
            newDown = self.north
            newNorth = self.up
            newSouth = self.down
            newEast = self.east #no change
            newWest = self.west #no change
        #Upward facing side of the die flips East
        elif (direction == "E"):
            newUp = self.west
            newDown = self.east
            newNorth = self.north #no change
            newSouth = self.south #no change
            newEast = self.up
            newWest = self.down
        elif (direction == "W"):
            newUp = self.east
            newDown = self.west
            newNorth = self.north #no change
            newSouth = self.south #no change
            newEast = self.down
            newWest = self.up
        self.up = newUp
        self.down = newDown
        self.north = newNorth
        self.south = newSouth
        self.east = newEast
        self.west = newWest
    
    def isValid(self, direction):
        if (direction == "S"):
            newUp = self.north
        elif (direction == "N"):
            newUp = self.south
        elif (direction == "E"):
            newUp = self.west
        elif (direction == "W"):
            newUp = self.east
        if (newUp == 6):
            return False
        return True
    
    def matches(self, die):
        if ( (self.up == die.getValue()) and (self.down == die.getDown()) and
             (self.north == die.getNorth()) and (self.south == die.getSouth()) and
             (self.east == die.getEast()) and (self.west == die.getWest()) ):
            return True
        return False
    
    def getValue(self):
        return self.up
    
    def getDown(self):
        return self.down
    
    def getNorth(self):
        return self.north
    
    def getSouth(self):
        return self.south
    
    def getEast(self):
        return self.east
    
    def getWest(self):
        return self.west

# the f(x) for the cost estimate of the A* search
def cost_estimate(node, board, h):
    heuristic_cost_basic(node, board)
    if (h == 1):
        hcost = heuristic_cost_basic(node, board)
    elif (h == 2):
        hcost = heuristic_cost_line(node, board)
    elif (h == 3):
        heuristic_cost_path(node, board)
    return node.getGx() + hcost

# the h(x) for the cost estimate of the A* search
# This heuristic just takes the absolute shortest distance
# between the current position and the goal without taking
# into account obstacles or the orientation of the die. This
# does take into account the actual steps needed to get to the goal
def heuristic_cost_basic(currNode, board):
    goal     = board.getGoal()
    position = currNode.getPosition()
    return (abs(goal[0] - position[0]) + abs(goal[1] - position[1]))

# the h(x) for the cost estimate of the A* search
# This heuristic just takes the straight line distance to the goal
# from the current position, not taking into account any obstacles
def heuristic_cost_line(currNode, board):
    goal     = board.getGoal()
    position = currNode.getPosition()
    x = goal[0] - position[0]
    y = goal[1] - position[1]
    return math.sqrt(x*x + y*y);

# the h(x) for the cost estimate of the A* search
# This heuristic is just a constant 0
def heuristic_cost_const():
    return 0

# recreates the path given a list of nodes traversed
def create_path(navigated, end):
    return None

def a_star(board, heuristic):
    node = Node(board.getStart(), Die(), board) #initial state node
    frontier = [node]   # next nodes to be evaluated
    visited = []        # nodes that have been visited
    numFrontNodes = 0   # number of nodes put on the frontier
    numVisitedNodes = 0  # number of nodes put on the visited list

    while (len(frontier) > 0):
        # get the node from frontier with the lowest f(x) cost
        node = frontier[0]
        for n in frontier:
            if (cost_estimate(n, board, heuristic) < cost_estimate(node, board, heuristic)):
                node = n
        frontier.remove(node)
        # if we are at the goal, return the path
        if((node.getPosition() == board.getGoal()) and (node.getDie().getValue() == 1)):
            print "Search stats (number of nodes put on frontier, number of nodes visited): (" + str(numFrontNodes) + "," + str(numVisitedNodes) + ")"
            return node.getPath()
        visited.append(node)
        numVisitedNodes = numVisitedNodes + 1
        # construct list of neighbor states
        children = node.getNeighbors()
        for child in children:
            Fcontains = False
            Vcontains = False
            # if frontier has the same child state, but with higher path cost, replace it with the child:
            for n in frontier:
                if (child.matches(n)):
                    Fcontains = True
                    if (cost_estimate(n, board, heuristic) > cost_estimate(child, board, heuristic)):
                        frontier.remove(n)
                        frontier.append(child)
                        numFrontNodes = numFrontNodes + 1
            for n in visited:
                if (child.matches(n)):
                    Vcontains = True
            # if neither our frontier nor our visited had the child state, add it to the frontier    
            if ((Fcontains == False) and (Vcontains == False)):
                frontier.append(child)
                numFrontNodes = numFrontNodes + 1

    # if the frontier is ever becomes empty, return failure
    print "Search stats (number of nodes put on frontier, number of nodes visited): (" + str(numFrontNodes) + "," + str(numVisitedNodes) + ")"
    return False
                
"""Main program"""
def main():
    b = Board()
    d = Die()
    if (len(sys.argv) < 2):
        filename = raw_input("Please specify a file name: ")
    else:
        filename = sys.argv[0]
    f = open(filename)
    for line in f:
        b.addRow(line)
    f.close()
    b.output()
    solution = a_star(b, 1) # 1 for running first heuristic, 2 for second heuristic, etc.
    if (solution == False):
        print "No Solution"
        return
    print "Nodes in solution: " + str(len(solution))
    print "Solution: ", solution
    
    #put 1 over start position
    b.makeMove(b.getStart()[0], b.getStart()[1], 1)
    b.output()
    #show each step
    for step in solution:
        d.move(step[2])
        b.makeMove(step[0], step[1], d.getValue())
        b.output()
main()
